abstract class Binsearch[+T] {
//The Ordered trait defines <, >, <=, and >= in terms of one method. Thus, trait Ordered //allows enrichment of a class with comparison methods by implementing only one method, //compare(line 6)
  def insert[U >: T <% Ordered[U]](x: U) : Binsearch[U] = this match {
    case End => Vert(x,End,End)
    case Vert(value, l, r) => {
      x.compare(value) match {
        case i if i < 0 => Vert(value, l.insert(x), r)
        case _ => Vert(value, l, r.insert(x))
      }
    }
  }

  
}

case class Vert[+T](value: T, l: Binsearch[T], r: Binsearch[T]) extends Binsearch[T] {
  override def toString = "T(" + value.toString + " " + l.toString + " " + r.toString + ")"
}

case object End extends Binsearch[Nothing] {
  override def toString = "."
}

object Vert {
  def Vert1[T](value: T): Vert[T] = Vert(value, End, End)
}

object Binsearch {

  def BinTree[T <% Ordered[T]](ls: List[T]) : Binsearch[T] = {
    ls.reverse match {
      case Nil => End
      case head :: xs => BinTree(xs.reverse).insert(head)
    }
  }

  

}

//this pogram inserts a node(vertex) in a binary search tree.
//BinTree forms a binary search tree from a given list.
//insert adds the node to the tree.